package someTestExcemple.huaweiOd.dp;
//华为OD机试 - 快递员的烦恼 - 动态规划（Java 2024 D卷 200分）
//https://blog.csdn.net/guorui_java/article/details/138141691
import java.util.*;
public class DeliveredTheGoods {
    /**
     * 2 1
     * 1 1000
     * 2 1200
     * 1 2 300
     *
     * 快递员先把快递送到客户1手中，接下来直接走客户1到客户2之间的直通线路，最后走投递站和客户2之间的路，回到投递站，距离为1000+300+1200= 2500
     */
    static final int MAX = 10001; // 一个比较大的数，用于表示无法直接到达
    static final int MAX_CLIENTS = 11; // 最多10个客户加上一个投递站

    public static int optimizeDelivery(int n, int m, int[][] deliveryInfo, int[][] customerDistances) {
        int V = n + 1; // 顶点总数，包括投递站和所有客户
        int[][] dist = new int[V][V]; // 存储最短路径的距离数组
        //由于0 < 客户id <= 1000
        //所以0号表示投递站

        // 初始化距离数组
        for (int i = 0; i < V; i++) {
            Arrays.fill(dist[i], MAX);
            dist[i][i] = 0; // 到自己的距离是0
        }

        // 填充投递站到客户的距离
        for (int[] info : deliveryInfo) {
            int clientId = info[0];
            int distance = info[1];
            dist[0][clientId] = distance;
            dist[clientId][0] = distance;
        }

        // 填充客户间的距离
        for (int[] custDist : customerDistances) {
            int cust1 = custDist[0];
            int cust2 = custDist[1];
            int distance = custDist[2];
            //考虑到cust1和cust2间可能有多条路线
            dist[cust1][cust2] = Math.min(dist[cust1][cust2], distance); // 取最小值，考虑重复边
            dist[cust2][cust1] = Math.min(dist[cust2][cust1], distance);
        }

        // 使用Floyd-Warshall算法计算所有点对的最短路径
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] < MAX && dist[k][j] < MAX) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        // 解决TSP问题
        int ALL_VISITED = (1 << n) - 1; // 全部访问过的状态
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) {
            Arrays.fill(row, MAX);
        }

        // 初始化，从投递站到所有客户的起始距离
        for (int i = 1; i < n; i++) {
            dp[1 << i][i] = dist[0][i + 1];
        }

        // 动态规划填表
        for (int mask = 0; mask <= ALL_VISITED; mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) { // 如果i已访问
                    for (int j = 0; j < n; j++) {
                        if ((mask & (1 << j)) == 0) { // 如果j未访问
                            int nextMask = mask | (1 << j);
                            dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + dist[i + 1][j + 1]);
                        }
                    }
                }
            }
        }

        // 从任何客户返回投递站的最短路径
        int minPath = MAX;
        for (int i = 0; i < n; i++) {
            minPath = Math.min(minPath, dp[ALL_VISITED][i] + dist[i + 1][0]);
        }

        return minPath == MAX ? -1 : minPath;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); //n个客户
        int m = scanner.nextInt(); //m条客户间路线
        int[][] deliveryInfo = new int[n][2];
        for (int i = 0; i < n; i++) {
            deliveryInfo[i][0] = scanner.nextInt(); //客户id
            deliveryInfo[i][1] = scanner.nextInt(); //客户距投递站距离
        }
        int[][] customerDistances = new int[m][3];
        for (int i = 0; i < m; i++) {
            customerDistances[i][0] = scanner.nextInt(); //客户1的id
            customerDistances[i][1] = scanner.nextInt(); //客户2的id
            customerDistances[i][2] = scanner.nextInt(); //客户1和2间的距离
        }
        int result = optimizeDelivery(n, m, deliveryInfo, customerDistances);
        System.out.println(result);
    }
}
